// 时间复杂度: 平均O(n2) 最坏O(n2) 最好O(n)
// 空间复杂度: O(1)
// 稳定性: 稳定排序


class InsertSort {
public:
    static void insertSort(int *array, int length) {
        for (int i = 1; i < length; ++i) {
            int value = array[i];
            for (int j = 0; j < i; j++) {
                if (value < array[j]) {
                    for (int k = i; k > j; --k) {
                        array[k] = array[k - 1];
                    }
                    array[j] = value;
                    break;
                }
            }
        }
    }
};